/*
 * @lc app=leetcode.cn id=931 lang=javascript
 *
 * [931] 下降路径最小和
 */

// @lc code=start
/**
 * @param {number[][]} matrix
 * @return {number}
 */
var minFallingPathSum = function (matrix) {
  const n = matrix.length;
  //   构建非同一引用的二维数组，注意不要用fill来构建子数组
  const curMin = Array.from({ length: matrix.length }, () =>
    Array.from({ length: matrix.length }, () => 0)
  );

  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
      if (i === 0) {
        curMin[i][j] = matrix[i][j];
        continue;
      }
      //   短路与Infinity的妙用
      curMin[i][j] =
        matrix[i][j] +
        Math.min(
          curMin[i - 1][j - 1] || Infinity,
          curMin[i - 1][j],
          curMin[i - 1][j + 1] || Infinity
        );
    }
  }
  return Math.min(...curMin[n - 1]);
};
// @lc code=end
